﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0158_EraseOverlapIntervals : IAlgorithm
    {
        // 435. 无重叠区间

        // 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

        // 提示:
        //  1 <= intervals.length <= 10^5
        //  intervals[i].length == 2
        //  -5 * 10^4 <= starti<endi <= 5 * 10^4

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(EraseOverlapIntervals());
        }

        // 算法
        public int EraseOverlapIntervals(int[][] intervals)
        {
            Array.Sort(intervals,
                (int[] a, int[] b) =>
                {
                    return a[1] - b[1];
                });

            int n = intervals.Length;
            int right = intervals[0][1];
            var ans = 1;
            for (int i = 1; i < n; ++i)
            {
                if (intervals[i][0] >= right)
                {
                    ++ans;
                    right = intervals[i][1];
                }
            }
            return n - ans;
        }
    }
}
